// Problem 167: Investigating Ulam sequences
//
// For two positive integers a and b, the Ulam sequence U(a,b) is defined by U(a,b)1 = a, U(a,b)2 = b and for k > 2, U(a,b)k is the smallest integer greater than U(a,b)(k-1) which can be written in exactly one way as the sum of two distinct previous members of U(a,b).
// For example, the sequence U(1,2) begins with
// 1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8;
// 5 does not belong to it because 5 = 1 + 4 = 2 + 3 has two representations as the sum of two previous members, likewise 7 = 1 + 6 = 3 + 4.
// Find ∑ U(2,2n+1)k for 2 ≤ n ≤10, where k = 10^11.

// ref: https://www.sciencedirect.com/science/article/pii/009731659290042S

// U(2,5):2 5 7 9 11 12 13 15 19 23 27 29 35 37 41 43 45 49 51 55 61 67 69 71 79 83 85 87 89 95 99 107
// general 2, v, v+2, v+4 ..... 2v-3, 2v-1,2v+1, 2v+2, 2v+3, 2v+5.....
// The second even integer term is k=(b+7)/2, and Uk = 2b + 2
// Fundamental difference D, Period N:
// 2n+1	D			N
// 5	126			32
// 7	126			26
// 9	1778		444
// 11	6510		1628
// 13	23,622		5906
// 15	510			80
// 17	507,842		126,960
// 19	1,523,526	380,882
// 21	8,388,606	2,097,152

package main

import (
	"fmt"
)

func p167() {
	D := []int{126, 126, 1778, 6510, 23622, 510, 507842, 1523526, 8388606}
	N := []int{32, 26, 444, 1628, 5906, 80, 126960, 380882, 2097152}
	ans := 0
	target := 100000000000
	for n := 2; n <= 10; n++ {
		// the Uk is even integer term, and its value is 4*n+4
		k := n + 4
		// the target's offset
		offset := (target - k) % N[n-2]
		// how many periods?
		np := (target - k) / N[n-2]
		x := ulam(n, k+offset)
		ans += x + np*D[n-2]
		//fmt.Printf("U(2,%d)%d=%d,Target:U(%d)+%d ans=%d\n", 2*n+1, k, 4*n+4, k+offset, np*D[n-2], ans)
	}
	fmt.Println("Problem 167:", ans)
	//ulam(2, 40)
}

//a=2,b=2*n+1
func ulam(n, k int) int {
	seq := []int{2}
	// remove the even integer term intentionally!!!
	even := 4*n + 4
	for x := 2*n + 1; x <= even+1; x += 2 {
		seq = append(seq, x)
	}
	for k > n+5 {
		last := seq[len(seq)-1]
		next := last + even
		flag := true
		for i := len(seq) - 1; i > 0; i-- {
			t := even + seq[i]
			if t > last+2 {
				if t < next {
					next = t
				}
			} else if t == last+2 {
				flag = false
			} else {
				seq = seq[i:]
				break
			}
		}
		if !flag {
			seq = append(seq, next)
		} else {
			seq = append(seq, last+2)
		}
		k--
	}
	//fmt.Println(seq)
	return seq[len(seq)-1]
}
